package cn.chen.算法.排序;

import java.util.Arrays;

/**
 * 希尔排序：将无序表按照一定增量进行分组，每分组一次就将每组数据进行插入排序，增量减小继续分组。继续插入排序，当增量=1的时候就只有一组了，最后一次插入排序就很简单了
 */
public class ShellSort {

    public static void main(String[] args){

        int [] arr={8,4,2,-8,5,12,0,25};
        System.out.println(Arrays.toString(arr));
        shellSort(arr);
        System.out.println(Arrays.toString(arr));

    }
    public static void shellSort(int[] arr){

        int temp = 0;
        for(int add=arr.length/2;add>=1;add/=2) {   // 利用循环来进行分组，增量越来越小，直到增量为1

            for (int i = add; i < arr.length; i++) {   // 从第二组的第一个元素开始遍历

                temp = arr[i];

                // 该if判断的作用就是用来提高效率的，如果temp比该组最后一个都大，那么该组就直接不用遍历了，就提高了效率。如果没有这个if那么还是会去遍历的
                /*if(temp<arr[i-add]) {   // 判断这一组最大的与要排序的该元素的大小（默认从小到大排序），需要移动才进入，不需要就不进入移动

                    for (int j = i - add; j >=0; j -= add) {    // 遍历这一组（从后往前遍历）的前面的元素,如果逆序就进行移动

                        if (temp < arr[j]) {    // 判断是否逆序

                            arr[j + add] = arr[j];  // 向后移动
                            arr[j] = temp;  // 插入的元素向前插入
                        }
                    }
                }*/
                int j=i-add;
                while(j>=0&&temp<arr[j]){   // 其实将上面的for循环该成下面的while循环，简化了代码，理解是一样的，&&之后的判断，在第一个不满足的情况下也不会进入循环，也提高了效率

                    arr[j + add] = arr[j];  // 向后移动
                    arr[j] = temp;  // 将要插入的元素插入到预定的位置
                    j-=add;
                }
            }
        }
    }
    public static void shellSort2(int[] arr){

        int temp = 0;
        for(int add=arr.length/2;add>=1;add/=2) {   // 利用循环来进行分组，增量越来越小，直到增量为1

            for (int i = add; i < arr.length; i++) {   // 从第二组的第一个元素开始遍历

                temp = arr[i];
                int j=i-add;
                while(j>=0&&temp<arr[j]){

                    arr[j + add] = arr[j];  // 向后移动
                    j-=add;
                }   // 循环结束之后j+add的位置就是要插入新元素的位置，不管循环有没有开始j+add都是正确的位置
                arr[j+add] = temp;  // 将要插入的元素插入到预定的位置
            }
        }
    }
}
